package dp.multi;

public class Solution_162 {
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        return dfs(m - 1, n - 1, memo);
    }

    private int dfs(int x, int y, int[][] memo) {
        if (x < 0 || y < 0) {
            return 0;
        }
        if (x == 0 && y == 0) {
            return 1;
        }
        if (memo[x][y] != 0) {
            return memo[x][y];
        }
        return memo[x][y] = dfs(x - 1, y, memo) + dfs(x, y - 1, memo);
    }

    public static void main(String[] args) {
        Solution_162 solution162 = new Solution_162();
        System.out.println(solution162.uniquePaths(3, 7));
    }
}
